package com.algorithm.learning.base.动态规划;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

/**
 * @program: algorithm-learning
 * @description: 这个题参考
 *              @see 打印字符串的所有子序列#process1(char[], int, List, String)
 *              只需要对子序列的结果进行去重即可
 * @author: YuKai Fan
 * @create: 2024/9/2 22:28
 **/
public class 打印字符串的所有子序列_不出现重复的字面值 {

    public static List<String> subs(String s) {
        char[] str = s.toCharArray();
        String path = "";
        Set<String> ans = new HashSet<>();
        process1(str, 0, ans, path);
        List<String> list = new ArrayList<>(ans);
        return list;
    }

    /**
     * 什么是子序列？
     * 一个字符串的子序列可以从任意字符的组合，但是必须满足原本字符串的字符栓寻
     *
     * 例如有一个字符串：abcd，它的子序列可以是：ab, ac, ad, abc, abcd, acd, abd, bc, bd...
     *
     * 但是不允许出现：ba, da, db, dc等，不满足字符串的原本字符的顺序
     *
     * 参考 => /img/打印字符串的所有子序列_1.png
     *
     * 这里的不重复字面值，意思就是子序列中不能出现重复的字符串，例如：aaa字符串
     *
     * 如果要0位置的a, 和1位置的a，不要2位置的a，那么子序列就是aa
     * 如果不要0位置的，要1位置的a和2位置的a，子序列也是aa
     * 这两个子序列就重复了，只要一个aa即可
     */
    public static void process1(char[] str, int index, Set<String> ans, String path) {
        if (index == str.length) {
            ans.add(path);
            return;
        }
        String no = path;
        process1(str, index + 1, ans, no);
        String yes = path + str[index];
        process1(str, index + 1, ans, yes);

    }
}
